# 166. 分数到小数
#
# 给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
#
# 如果小数部分为循环小数，则将循环的部分括在括号内。
#
# 如果存在多个答案，只需返回 任意一个 。
#
# 对于所有给定的输入，保证 答案字符串的长度小于 10^4 。


class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        result_positive = True
        if numerator / denominator < 0:
            result_positive = False

        before_point = 0
        numerator = abs(numerator)
        denominator = abs(denominator)
        if numerator > denominator:
            before_point = int(numerator / denominator)
            numerator = numerator - before_point * denominator

        after_point = []
        numerator_index = {}
        cycle_begin_index = -1

        for i in range(0, 10000):
            numerator = numerator * 10
            if numerator == 0:
                break
            if numerator in numerator_index:
                cycle_begin_index = numerator_index[numerator]
                break
            numerator_index[numerator] = i
            divided = int(numerator / denominator)
            after_point.append(divided)
            numerator = numerator - divided * denominator

        result = str(before_point)
        if not result_positive:
            result = "-" + result
        if len(after_point) == 0:
            return result

        result = result + "."
        for index in range(0, len(after_point)):
            if index == cycle_begin_index:
                result = result + "("
            result = result + str(after_point[index])
        if cycle_begin_index != -1:
            result = result + ")"
        return result
